/*
 * Copyright 2016 Scalified <http://www.scalified.com>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//package com.scalified.tree;
package com.gitee.wsl.struct.tree

import com.gitee.wsl.struct.node.Node

/**
 * This interface represents the basic tree data structure
 * <h1>Definition</h1>
 * A tree data structure can be defined recursively (locally) as a collection of nodes
 * (starting at a root node), where each node is a data structure consisting of a value,
 * together with a list of references to nodes (the children), with the constraints that
 * no reference is duplicated, and none points to the root
 *
 *
 * A tree is a (possibly non-linear) data structure made up of nodes or vertices and edges
 * without having any cycle. The tree with no nodes is called the **null** or
 * **empty** tree. A tree that is not empty consists of a root node and potentially many
 * levels of additional nodes that form a hierarchy
 * <h1>Terminology</h1>
 *
 *  * **Node** - a single point of a tree
 *  * **Edge** - line, which connects two distinct nodes
 *  * **Root** - top node of the tree, which has no parent
 *  * **Parent** - a node, other than the root, which is connected to other successor
 * nodes
 *  * **Child** - a node, other than the root, which is connected to predecessor
 *  * **Leaf** - a node without children
 *  * **Path** - a sequence of nodes and edges connecting a node with a
 * descendant
 *  * **Path Length** - number of nodes in the path - 1
 *  * **Ancestor** - the top parent node of the path
 *  * **Descendant** - the bottom child node of the path
 *  * **Siblings** - nodes, which have the same parent
 *  * **Subtree** - a node in a tree with all of its proper descendants, if any
 *  * **Node Height** - the number of edges on the longest downward path between that
 * node and a leaf
 *  * **Tree Height** - the number of edges on the longest downward path between the
 * root and a leaf (root height)
 *  * **Depth (Level)** - the path length between the root and the current node
 *  * **Ordered Tree** - tree in which nodes has the children ordered
 *  * **Labeled Tree** - tree in which a label or value is associated with each node
 * of the tree
 *  * **Expression Tree** - tree which specifies the association of an expression�s
 * operands and its operators in a uniform way, regardless
 * of whether the association is required by the placement
 * of parentheses in the expression or by the precedence and
 * associativity rules for the operators involved
 *  * **Branching Factor** - maximum number of children a node can have
 *  * **Pre order** - a form of tree traversal, where the action is called firstly on
 * the current node, and then the pre order function is called again
 * recursively on each of the subtree from left to right
 *  * **Post order** - a form of tree traversal, where the post order function is called
 * recursively on each subtree from left to right and then the
 * action is called
 *
 *
 * @author shell
 * @version 1.0.0
 * @since 1.0.0
 */
abstract class TreeNode : Node<Any?> {
    /**
     * Reference to the parent tree node. Is `null` if the current tree node is root
     */
    open var parent: CategoryTreeNode? = null

    protected var level = UNDEFINE

    /**
     * Creates an instance of this class
     *
     * @param data data to store in the current tree node
     */
    constructor(data: Any?) : super(data)

    constructor() : super()

    /**
     * Checks whether the current tree node is the root of the tree
     *
     * @return `true` if the current tree node is root of the tree;
     * `false` otherwise
     */
    val isRoot: Boolean
        get() = parent == null

    /**
     * Returns the root node of the current node
     *
     *
     * Returns itself if the current node is root
     *
     * @return root node of the current node; itself,
     * if the current node is root
     */
    fun root(): TreeNode {
        if (isRoot) {
            return this as TreeNode
        }
        var current :TreeNode = this as TreeNode
        var node : TreeNode? = current
        do {
            node?.let { current = it }
            node = node?.parent
        } while (node!=null&&!node.isRoot)
        return current
    }

    /**
     * Returns the parent node of the current node
     *
     *
     * Returns `null` if the current node is root
     *
     * @return parent node of the current node; `null`
     * if the current node is root
     */
    /*fun parent(): TreeNode? {
        return parent
    }*/

    /**
     * Checks whether the current tree node is a leaf, e.g. does not have any
     * subtrees
     *
     * @return `true` if the current tree node is a leaf, e.g. does not
     * have any subtrees; `false` otherwise
     */
    open val isLeaf: Boolean
        get() = true

    /**
     * Returns the number of nodes in the entire tree, including the current tree node
     *
     * @return number of nodes in the entire tree, including the current tree node
     */
    open fun size(): Long {
        return 1
    }

    /**
     * Returns the height of the current tree node, e.g. the number of edges
     * on the longest downward path between that node and a leaf
     *
     * @return height of the current tree node, e.g. the number of edges
     * on the longest downward path between that node and a leaf
     */
    open fun height(): Int {
        return 0
    }

    /**
     * Returns the depth (level) of the current tree node within the entire tree,
     * e.g. the number of edges between the root tree node and the current one
     *
     * @return depth (level) of the current tree node within the entire tree,
     * e.g. the number of edges between the root tree node and the current
     * one
     */
    open fun level(): Int {
        if (isRoot) {
            level = 0
        } else if (level == UNDEFINE) level = parent!!.level + 1
        return level
    }

    /**
     * Creates and returns a copy of this object
     *
     * @return a clone of this instance
     */
     /*override fun clone(): TreeNode {
        return try {
            super.clone() as TreeNode
        } catch (e: CloneNotSupportedException) {
            val message = "Unable to clone the current tree node"
            throw TreeNodeException(message, e)
        }
    }*/

    /**
     * Indicates whether some object equals to this one
     *
     * @param obj the reference object with which to compare
     * @return `true` if this object is the same as the obj
     * argument; `false` otherwise
     */
    override fun equals(obj: Any?): Boolean {
        if (this === obj) {
            return true
        }
        if (obj == null
            || this::class != obj::class
        ) {
            return false
        }
        val that = obj as TreeNode
        return nodeId == that.nodeId
    }

    /**
     * Returns the hash code value of this object
     *
     * @return hash code value of this object
     */
    override fun hashCode(): Int {
        return (nodeId xor (nodeId ushr 32)).toInt()
    }

    /**
     * Returns the string representation of this object
     *
     * @return string representation of this object
     */
    override fun toString(): String {
        val builder = StringBuilder()
        builder.append("\n")
        val topNodeLevel = level()
        val action: TraversalAction<TreeNode> = object : TraversalAction<TreeNode> {
            override fun perform(node: TreeNode) {
                val nodeLevel = node.level() - topNodeLevel
                for (i in 0 until nodeLevel) {
                    builder.append("|  ")
                }
                builder
                    .append("+- ")
                    .append(node.data)
                    .append("\n")
            }

            override val isCompleted: Boolean
                get() = false
        }
        traversePreOrder(this, action)
        return builder.toString()
    }

    fun traversePreOrder(action: TraversalAction<TreeNode>) {
        traversePreOrder(this, action)
    }


    protected open fun traversePreOrder(node: TreeNode, action: TraversalAction<TreeNode>) {

    }

    fun traversePostOrder(action: TraversalAction<TreeNode>) {
        traversePostOrder(this , action)
    }

    protected open fun traversePostOrder(node: TreeNode, action: TraversalAction<TreeNode>) {}

    open operator fun contains(node: TreeNode): Boolean {
        return false
    }

    open fun remove(node: TreeNode): Boolean {
        return false
    }

    open var children: MutableList<TreeNode> = mutableListOf()

    //open fun getChildren(): List<TreeNode> = emptyList()

    companion object {
         const val UNDEFINE = -1
    }
}